Phố này được xây dựng trên nền đất thuộc các thôn: Vĩnh Xương, Nam Môn, Hoa Ngư, Tứ Mỹ vào năm 1879. Thời Pháp thuộc quen gọi là đường Quan Lộ. Đến thế kỉ XIX, thôn Nam Môn và thôn Thụy Hoa Ngừ đổi thành thôn Nam Ngư. Đến 1947 đường này đổi là Đờ Lát Sơ (Delatte Sir). Người dân trên phố này thường quen gọi là phố Hàng Lọng.

Sau năm 1954, chính quyền thành phố Hà Nội đổi thành đường Nam Bộ, với một ý nghĩa rất sâu sắc: đây là con đường có ga Hà Nội, nơi xuất phát của các chuyến tàu vào Nam Bộ. Tên đường Nam Bộ đã xuất hiện trong bài thơ "Bài ca Xuân 1961" của nhà thơ Tố Hữu:

Tôi viết cho ai bài thơ 61?

Đêm đã khuya rồi, rét về tê buốt

Hà Nội rì rầm... Còi thổi ngoài ga

Một chuyến tàu chuyển bánh đi xa

Tiếng xình xịch, chạy dọc đường Nam Bộ...

Cái tên này kết hợp với các địa danh khác quanh khu vực như Công viên Thống Nhất, đường Giải Phóng, đảo Hòa Bình (trong Công viên Thống Nhất), v.v... đã tạo thành một quần thể địa danh, thể hiện rõ khát vọng thống nhất nước Việt Nam thời đó.

Để tưởng nhớ Tổng bí thư Lê Duẩn, chính quyền thành phố Hà Nội quyết định đổi tên đường Nam Bộ thành đường Lê Duẩn. Đồng thời, Công viên Thống Nhất bị đổi tên thành công viên Lê Nin, khiến cho tính thống nhất về mặt địa danh ở đây bị phá vỡ. Tuy nhiên, sau này, Công viên Thống Nhất đã được trả lại tên cũ, còn tên công viên Lê Nin được đổi sang cho vườn hoa Chi Lăng nơi có tượng đài Lê Nin.